﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

// 找出字符串中第一个匹配的下标
class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        if (haystack.size() < needle.size()) return -1;
        int left = 0, i = 0;
        while (left < haystack.size() - needle.size() + 1)
        {
            int cur = left; // 记录匹配的起始位置
            while (i < needle.size() && haystack[cur] == needle[i])
            {
                cur++;
                i++;
            }
            if (i == needle.size()) return left;
            // 匹配的位置++,匹配的字符串位置从0开始
            else
            {
                i = 0;
                left++;
            }
        }

        return -1;
    }
};

// 有效的字母异位词
class Solution
{
public:
    bool isAnagram(string s, string t)
    {
        if (s.size() != t.size()) return false;
        unordered_map<char, int> hash;
        for (auto ch : s)
        {
            hash[ch]++;
        }
        for (auto ch : t)
        {
            if (hash[ch] > 0) hash[ch]--;
            else return false;
        }
        return true;
    }
};

//字母异位词分组
class Solution
{
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs)
    {
        unordered_map<string, vector<string>> hash;
        // 1. 把所有的字⺟异位词分组
        for (auto& s : strs)
        {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(s);
        }

        // 2. 结果提取出来
        vector<vector<string>> ret;
        for (auto& [x, y] : hash)
        {
            ret.push_back(y);
        }

        return ret;
    }
};

// 快乐数-快慢指针
class Solution
{
public:
    int sum(int n)
    {
        int ret = 0;
        while (n)
        {
            int tmp = (n % 10) * (n % 10);
            ret += tmp;
            n /= 10;
        }

        return ret;
    }
    bool isHappy(int n)
    {
        int slow = n, fast = sum(n);
        while (slow != fast)
        {
            slow = sum(slow);
            fast = sum(sum(fast));
        }
        return slow == 1;
    }
};

//存在重复元素
class Solution
{
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++)
        {
            if (hash.count(nums[i]))
            {
                if (i - hash[nums[i]] <= k)
                    return true;
            }

            hash[nums[i]] = i;
        }

        return false;

    }
};

//滑动窗口解法
class Solution
{
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        unordered_set<int> st;
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            if (i > k)
            {
                st.erase(nums[i - k - 1]);
            }
            // 判断
            if (st.count(nums[i]))
                return true;
            // 进窗口
            st.emplace(nums[i]);

        }

        return false;
    }
};

//汇总区间
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ret;
        int n = nums.size();
        int left = 0, right = 0;
        for (int i = 0; i < n;) {
            left = right = i;
            while (right + 1 < n && nums[right + 1] == nums[right] + 1) {
                right++;
            }
            if (left != right) {
                ret.push_back(to_string(nums[left]) + "->" + to_string(nums[right]));
            }
            else {
                ret.push_back(to_string(nums[left]));
            }
            i = right + 1; // 更新 i 的值
        }
        return ret;
    }
};

int main()
{
    return 0;
}